package _go

/*剑指 Offer II 003. 前 n 个数字二进制中 1 的个数
难度
简单

19

收藏

分享
切换为英文
接收动态
反馈
给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。



示例 1:

输入: n = 2
输出: [0,1,1]
解释:
0 --> 0
1 --> 1
2 --> 10
示例 2:

输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101


说明 :

0 <= n <= 105*/

func countBits(n int) []int {
	if n == 0 {
		return []int{0}
	}
	res := make([]int, n+1)
	res[0] = 0

	for i := 1; i <= n; i++ {
		// i & i -1 是把i 的二进制最后一位消掉
		//所以  这个就是 一点点递归的过程
		res[i] = res[i&(i-1)] + 1
	}
	return res
}
